/*
题目链接:https://leetcode.cn/problems/domino-and-tromino-tiling/description/?envType=daily-question&envId=2025-05-05
*/

//题解代码:
class Solution {
public:
    const int mod = 1e9+7;
    int f[1002][4];
    int dfs(int i,int s){
        if(i==0) return s==0;
        if(f[i][s] != -1) return f[i][s];
        long long ret = 0;
        if(s==0){
            ret = ret + dfs(i-1,0) + dfs(i-1,1) + dfs(i-1,2) + dfs(i-1,3);
        }else if(s==1){
            ret = ret + dfs(i-1,3) + dfs(i-1,2);
        }else if(s==2){
            ret = ret + dfs(i-1,1) + dfs(i-1,3);
        }else{
            ret = ret + dfs(i-1,0);
        }
        ret %= mod;
        f[i][s] = ret;
        return ret;
    }
    int numTilings(int n) {
        memset(f,-1,sizeof(f));
        return dfs(n,0);
    }
};
